package jianzhiOffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//剑指 Offer 38. 字符串的排列
public class Num38_permutation {
    private List<String>res = new ArrayList<>();
    boolean[]used;
    public String[] permutation(String s) {
        this.used = new boolean[s.length()];
        StringBuilder sb = new StringBuilder();
        char []arr = s.toCharArray();
        Arrays.sort(arr);
        backTracking(arr , 0 , sb);
        String[]result = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
    public void backTracking(char[]arr,int j , StringBuilder sb){
        if (j == arr.length){
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (used[i] || (i > 0 && !used[i - 1] && arr[i - 1] == arr[i])){
                continue;
            }else {
                used[i] = true;
                sb.append(arr[i]);
                backTracking(arr , j + 1 , sb);
                sb.deleteCharAt(sb.length() - 1);
                used[i] = false;
            }
        }
    }
}
